﻿/**	\file		std_algorithm.hpp
 *	\date		(2009-07-08 20:30:27)/(2014-11-29 15:34:15)
 *-----------------------------------------------------------------------------
 *	\version	1.0.3.8
 *	\author		Nick Shallery	(nicknide@gmail.com)
 *	\copyright	YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.
 *-----------------------------------------------------------------------------
**/

#if			!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)
#define		__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__

//==============================================================================
//--------------------------------------------------------------------------

#if			!defined(__LOLIX__LOLIX_SUPPORTED__HPP__K_IN_G__)
	#include	"../_lolix_supported.hpp"
#endif	//	!defined(__LOLIX__LOLIX_SUPPORTED__HPP__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)
	#include	"./std_functional.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)

namespace lolix{namespace toy{
	template<typename _TyBegin, typename _TyEnd, typename _TyValue, typename _TyCmp>
	_TyBegin lower_bound(_TyBegin bg, _TyEnd ed, _TyValue const& val, _TyCmp cmp)
		{
		while ( bg != ed )
			{
			_TyBegin iter = bg + (ed - bg)/2;
			if ( cmp(*iter, val) )
				++(bg = iter);
			else
				ed = iter;
			}

		return bg;
		}

	template<typename _TyBegin, typename _TyEnd, typename _TyValue>
	_TyBegin lower_bound(_TyBegin bg, _TyEnd ed, _TyValue const& val)
		{
		return lower_bound(bg, ed, val, less());
		}

	template<typename _TyBegin, typename _TyEnd, typename _TyValue, typename _TyCmp>
	_TyBegin upper_bound(_TyBegin bg, _TyEnd ed, _TyValue& val, _TyCmp cmp)
		{
		while ( bg != ed )
			{
			_TyBegin iter = bg + (ed - bg)/2;
			if ( cmp(val, *iter) )
				ed = iter;
			else
				++(bg = iter);
			}

		return bg;
		}

	template<typename _TyBegin, typename _TyEnd, typename _TyValue>
	_TyBegin upper_bound(_TyBegin bg, _TyEnd ed, _TyValue& val)
		{
		return upper_bound(bg, ed, val, less());
		}



	template<typename _Ty>
	LOLIX_INLINE_CALL const _Ty& (min)(const _Ty& l, const _Ty& r)
		{
		return l < r ? l : r;
		}

	template<typename _Ty>
	LOLIX_INLINE_CALL const _Ty& (max)(const _Ty& l, const _Ty& r)
		{
		return l < r ? r : l;
		}

	template<typename _IterL, typename _IterR, typename _Twork>
	LOLIX_INLINE_CALL void for_each(_IterL const& b, _IterR const& e, _Twork& work)
		{
		for (auto iter = b; iter != e; ++iter)
			work(*iter);
		}

	template<typename _IterL, typename _IterR, typename _Tval>
	LOLIX_INLINE_CALL _IterL find(_IterL b, _IterR e, _Tval const& v)
		{
		for (auto iter = b; iter != e; ++iter)
			if (*iter == v)
				return iter;
		return e;
		}

	template<typename _Iter, typename _TCmp>
	LOLIX_INLINE_CALL void sort(_Iter b, _Iter e, _TCmp const& cmp)
		{
		if ( b == e )
			return;
		--e;
		if ( b == e )
			return;

		auto iter_last = e;
		--iter_last;
		if ( iter_last == b )
			{
			if ( cmp(*e, *iter_last) )
				swap(*iter_last, *e);
			return;
			}

		for ( auto iter = b; iter != iter_last; )
			{
			for ( ; iter != iter_last; ++iter )
				if ( cmp(*e, *iter) )
					break;

			for ( ;iter != iter_last; --iter_last )
				if ( cmp(*iter_last, *e) )
					break;

			if ( iter != iter_last )
				{
				swap(*iter, *iter_last);
				++iter;
				if ( iter == iter_last )
					break;
				--iter_last;
				}
			}

		if ( cmp(*e, *iter_last) )
			swap(*iter_last, *e);
		++iter_last;
		sort(b, iter_last, cmp);
		sort(iter_last, ++e, cmp);
		}

	template<typename _Iter>
	LOLIX_INLINE_CALL void sort(_Iter b, _Iter e)
		{
		sort(b, e, less());
		}


	template<typename Ipt>
	LOLIX_INLINE_CALL void reverse(Ipt s, Ipt e)
		{
		for (; s != e && s != --e; ++s)
			swap(*s, *e);
		}

	template<typename _Iter>
	LOLIX_INLINE_CALL _Iter unique(_Iter b, _Iter e)
		{
		return unique(b, e, equal());
		}
	template<typename _Iter, typename _TCmp>
	LOLIX_INLINE_CALL _Iter unique(_Iter b, _Iter e, _TCmp const& cmp)
		{
		if ( b == e )
			return e;
		_Iter n(b);
		for ( ++n ; n != e; ++n)
			if ( !cmp(*b, *n) )
				{
				++b;
				if ( b != n )
					discard_copy(*b, *n);
				}
		return ++b;
		}
}}


//--------------------------------------------------------------------------
//==============================================================================
#endif	//	!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)
